A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
This invention relates to the formatting of digital data into a pattern, encoding that pattern onto a substrate where appropriate, and decoding the pattern to reconstruct the digital data.
While computers have substantially enhanced the manner in which society conveys and works with information, paper remains the favored manner of conveying information. Indeed, the proliferation of personal computers has resulted in a proliferation of paper. Yet, no technology to date has significantly integrated the digital environment of the computer with the visual environment of written media. Instead, computers primarily direct human readable information to be placed on paper.
It would be greatly advantageous to have digital data placed on paper and other media currently used for human readable information. Such a method would link the largely separate environments of paper and computers. The method could store and convey digital data with greater efficiency, ease, speed, and lesser cost than any other available method. The method would have the further advantage of being the only significant method to integrate digital data with visual media.
As described below, the prior art discloses methods for placing machine readable information on media such as paper. However, none of these prior art methods, and, to the best of the inventors"" knowledge, no other technology currently available to personal computer users allows for the placement of a significant amount of machine readable information on the media. Other practical limitations of these prior art methods forestall significant commercial success.
One example of digital information being stored on paper is the use of bar codes. Because standard bar codes are one dimensional, they are severely limited in the number of bars that may be used to store digital information. The limits are somewhat greater in the case of two-dimensional bar codes but these limits are still far more restrictive than the theoretical limits of any particular printer, and bar codes are designed for use with specialized scanners. For more information on bar codes, see xe2x80x9cInformation Encoding with Two-Dimensional Bar Codes,xe2x80x9d authored by T. Pavlidis, J. Schwartz and Y. Wang, COMPUTER, June 1992.
U.S. Pat. No. 5,245,165, issued to Zhang, discloses a self-clocking glyph code for encoding dual bit digital values of a logically ordered sequence of wedge-shaped glyphs that are written or otherwise recorded on a hardcopy recording medium in accordance with a predetermined spatial formatting rule. The dual bit values are encoded in the relative rotations of the glyphs. The glyphs are decoded by determining a bounding box for each glyph and determining either which quadrant of the box contains its center of mass or by comparing the relative locations of the shortest and longest runs of ON pixels. To reliably present a single bit of data, each glyph comprises a large number of pixels, and thus this technology requires considerable space on the recording medium. The technology does not optimize the use of space or computational resources by presenting a bit in the most compact fashion.
U.S. Pat. No. 5,337,362, issued to Gormish, discloses a method for transferring digital information to and from plain paper. The method involves storing data in at least one box on the paper, the box including a frame or border having alternating pixels along the left and right edges for use in determining the current location of a horizontal line of pixels when reading the data and having pixels in corners of the frame to determine horizontal spacing between pixels within the box. Binary data is formatted in rows within the box, wherein a bit of digital data is depicted by the presence or absence of an ink dot. The method disclosed by Gormish provides the ability to represent 60 kilobytes of data on a single page.
Although Gormish allows for the storage of more data on a page than can currently be stored in text form, it has several problems which prevent it from being useful in a commercial environment. For example, Gormish requires a thick frame to be placed around the entire data box in order to locate the box, which limits the ability to place the data in convenient shapes and sizes on a substrate. Also, Gormish requires placement of pixels in a rigid fashion, without provision of guideposts to determine where to search for the presence or lack of a dot other than on the borders of the boxes. Further, Gormish provides ink placement in an ink dot that covers an entire square and that square covers an area 16 times larger than the finest optical resolution of any given scanner (e.g., Gormish discloses printing dots at 50 dpi while scanning is performed at 200 dpi), thereby limiting the density of data which can be represented on each page. In addition, although the method disclosed in Gormish may be suited for certain printers and scanners of great precision it does not adequately accommodate for deviations from perfection in printing and scanning found in off-the-shelf printers and scanners designed for use with personal computers. Operating in an environment of personal computers and their peripherals, this rigidity ultimately translates into loss of data density, higher error rates, slower processing speed, all of these deficiencies, or, worse yet, complete inability to use the method in given computer environments.
Other known methods disclose manners in which a single cell contains more than one bit of information through the use of gray scales. One such method is disclosed in U.S. Pat. No. 5,278,400, issued to J. Appel (1994). This patent discloses the encoding of multiple bits in a single cell by marking, preferably by binary marking, a predetermined number of pixels in a cell irrespective of the location of the pixels within the cell. The number of pixels marked corresponds to the data to be encoded. The markings on the substrate are decoded by detecting the gray scale level at each pixel of the cell, converting that gray scale level to a corresponding digital signal and summing all of the digital signals corresponding to all of the pixels in the cell. This method requires discrete determination of where the cell begins and ends. The gains from encoding multiple values in a single cell are lost by requiring larger cells, relative to straightforward binary printing. Gormish also discloses the encoding of multiple values in one cell through the use of gray scale inks. This method employs rigid formatting and printing described above and similarly relies on rigid decoding mechanisms that may be optimized for a particular combination of a printer and a scanner, but not for all such combinations. These methods give back the data density and savings in computational resources that the use of multiple colors should provide.
U.S. Pat. Doc. No. 5,329,107, issued to D. Priddy and R. Cymbalski (1994), discloses a method to dynamically vary the size, format, and density of machine readable binary code. The method disclosed in that document provides a code formed of a matrix and allows variation in the amount of data in the matrix by printing on two sides of the perimeter of the matrix broken line patterns of alternating darkened and lightened areas. The method determines the amount of data in the matrix from the product of the number of lightened areas and darkened areas of the first side and the number of lightened areas and darkened areas of the second. The method determines size of the matrix by measuring the other two sides of the perimeter, formed of two solid black lines. While the method allows the encoder of information some flexibility in accommodating the different potentials of higher and lower resolution scanners, the method is rigid in darkening entire square cells. The method also lacks regular reference markers and generally limits information about the encoding, conveyed in the matrix, to size and density. The method therefore lacks the flexibility needed to address the peculiarities of every combination of printer and scanner. Hence the method can not produce the greatest density of data or the most efficient manner of decoding for every combination of printer and scanner.
There is a need to substantially increase the amount of data that can be stored within a given amount of paper in order to compete with other channels of storage and communication such as floppy disks and digital communication by telephone. Employing binary printing (i.e., storing one bit per cell), the most basic and least dense printing process, the invention is capable of storing data at densities several times as great as any other paper based method known to the inventors. Utilizing printing methods which store more than one bit per cell, such as color printing, the theoretical density limits increase substantially.
While Gormish discloses the ability to store 60 kilobytes on a single page using a 400 dpi scanner, the invention is capable of encoding and decoding over 160 kilobytes of data error free (i.e., by utilizing error correction) using just a 300 dpi scanner. With the aid of compression, this single page can contain over 500 kilobytes of text. With a 600 dpi printer and a 600 dpi flatbed scanner, the invention can encode data in cells {fraction (1/200)} inch square (i.e., 0.005 inchxc3x970.005 inch), successfully encoding and decoding over 300 kilobytes of data before the benefit of any compression, in excess of 1 megabyte of text with the aid of compression. Utilizing more precise printing processes and a 600 dpi flatbed scanner, the invention encodes and decodes over 7,000 bytes per square inch (over 1,100 bytes/cm2), over 20,000 bytes of text using compression. Utilizing an ordinary thermal fax machine as a scanner (achieving a binary scan of approximately 200 dpi), the invention encodes and decodes over 50 kilobytes of data, over 150 kilobytes of text with the aid of compression. All of the above densities are accomplished utilizing binary printing.
The invention also conveys advantages for any particular printer. For example, using an ordinary thermal fax machine the invention can print over 230 kilobytes of data, over 675 kilobytes of text with compression, on an 8.5 by 11 in. piece of thermal fax paper. The invention can then successfully decode that data error free.
It is an object of the present invention to solve the problems discussed above present in prior art systems for representing digital data on a substrate.
It is another object of the present invention to greatly increase the density at which digital data can be represented on a substrate.
It is another object of this invention to overcome the limitations of prior art through a method that writes and reads digital data on paper and other media using off-the-shelf personal computers and peripherals, and achieves the full carrying capacity these off-the-shelf components can sustain.
It is another object of the invention to determine and enable the features and parameters that contribute to density of information on a printed substrate, and to enable full generality in formatting and decoding along the dimensions identified. This satisfies in turn the ultimate, practical goal: achieving the maximum density possible for any particular combination of printer and scanner. This comes about because that point of maximum density can always be found in the multi-dimensional space so defined.
It is another object of the present invention to provide flexibility in printing digital data onto a substrate along with other information.
These and other objects of the invention are achieved by a method of formatting digital data into a pattern where the pattern comprises a number of cells (i.e., predetermined spaces in the pattern) with known dimensions where each cell conveys at least one bit of data by expressing one of at least two logical states where one logical state is expressed by the presence of spot with a given set of attributes in the cell and a second logical state is expressed by the absence of a spot with those attributes from the cell, and where the size of spots may be different from the size of cells containing the spots.
Generally speaking, in accordance with the invention, a method of formatting data into a pattern in an optimal fashion is provided. The preferred embodiment of the invention provides for the placement of ink on paper. The preferred embodiment allows the person providing data to format the placement of digital data. This flexibility in formatting the placement of digital data allows the person providing data to optimize for any particular combination of encoding device and scanner. The method of encoding allows the person providing data to format the placement of ink in a fashion that best reflects the printer""s capabilities to place ink in a designated area. The method of encoding also allows for formatting designed to consider the strengths and limitations of the target audience of scanners.
The features that support encoding information on the printed substrate, and its effective decoding via a scanner, fall under two heads. First, there are dark regions on the substrate, which the current invention terms xe2x80x9cspots,xe2x80x9d whose presence or absence in a specified region represents digital bits. Second, there are guideposts, which the present invention terms xe2x80x9cmarkers,xe2x80x9d that serve to identify the location of spots on the printed substratexe2x80x94a function known in the art as xe2x80x9cclocking.xe2x80x9d The present invention explicitly decouples these two features, allowing them to be varied independently, so that each may be optimally configured for its distinct purpose. The current invention also permits each to be varied across all the dimensions (e.g., those defining size, spacing, and frequency) that affect the density of information on the printed substrate, while supporting its effective decoding. This full generality allows the optimum match for a particular printer and scanner always to be selected, formatted, and decoded.
The method of the present invention allows the person or computer encoding data to select the size, in pixels, of both the cell containing a bit of information and the size of the printed spot where a spot is required. The preferred embodiment of the method of encoding provides a bit of one value by placing a spot of the chosen size in the cell of the chosen size. The method provides a bit of the opposite value by leaving the cell of the chosen size blank. In accordance with the invention, the size of the spots and of the cells can be varied in both the width and height directions.
The method of the present invention also allows the person or computer system encoding data to select the size and locations of markers. In accordance with the invention, the size and location of the markers can be flexibly altered to achieve reliable clocking with the minimum amount of space and computation time.
The method of the preferred embodiment provides information about the encoding process through use of a xe2x80x9cmetasectorxe2x80x9d, a header physically separate from the main body of data. The purpose of providing a metasector is to facilitate decoding the main body of data. In this embodiment, the metasector is itself an instance of the general pattern by which information is stored in the invention. This metasector is preferably printed at a resolution which can be easily and reliably scanned and interpreted. It is also given a predictable and relatively rigid format, which makes it straightforward to decode in the absence of detailed information about the printing process and environment which generated the encoded data. This metasector contains information about the printing process and environment that is then used to decode the main body of data. The somewhat rigid format of the metasector frees the main body of the data from rigidity in its own format, allowing it the greatest flexibility in achieving maximum density. The metasector, encoded at a relatively low resolution, contains information communicated to the remainder of the method in order to decode information at a higher resolution. The information included in the metasector includes, inter alia, the size of the data spots printed, the size of the cells containing data spots, the printing process used to print spots and the size and relative location of markers, if any.
Allowing flexibility in the size and placement of data spots in cells greatly increases density of data and improves the speed and accuracy of determining whether a bit is on or off. The fundamental purpose behind defining spot size independently is twofoldxe2x80x94first, to compensate for printer deficiencies and, second, to compensate for scanner deficiencies.
Within types of printers, such as 300 dot-per-inch (xe2x80x9cdpixe2x80x9d) laser printers, there is variation in both the ability to place ink at a given location and the ability to keep ink within the spot designated by that location. For example, printers have varying degrees of xe2x80x9cdot gainxe2x80x9dxe2x80x94the tendency of most printers to place ink beyond the purported boundaries of the pixel. Dot gain, and the problems it causes, can be exacerbated when the printing process employed goes through multiple steps. If, for example, the printing process involves producing film from a print, a plate from film, and copies from the plate, increasing amounts of dot gain can occur in each step. A spot is preferably allowed to be defined to be smaller than its cell (i.e., the space that is supposed to contain the spot) simply to prevent spots from spilling over to adjacent cells.
Even with perfect printing, however, it would be important to allow smaller spots than cells, because of a second phenomenon. Scanners characteristically xe2x80x9cleakxe2x80x9d dark intensities from one pixel to a directly adjacent pixel. That is, if a pixel is directly over a dark region on the printed substrate, and an adjacent pixel is not, the intensity of the adjacent pixel is nonetheless suppressed to a darker value. When spots completely fill in their cells, the cells must be made larger to compensate for this tendency of scanners. If they are not made larger, the neighboring cell when blank may not differ enough in intensity from the dark cell to be discriminated as blank. Making it possible to configure spots to be smaller than cells generally allows cells to be smaller while supporting correct discrimination between dark and white cells.
Of course, it is possible in principle that a given printer (or a like device) may characteristically print smaller spots than defined, or a given scanner (or a like device) may xe2x80x9cleakxe2x80x9d bright intensitiesxe2x80x94in which case it would be useful to define spots to be marginally larger than the cells they occupy (or, alternatively, to print spots in reverse video.)
Between types of scanners or types of printers, such as between a 360 dpi inkjet printer and a 600 dpi laser, the degree of variation expands significantly. Laser printers have a greater precision in the placement of ink, and 600 dpi printers place ink more accurately than a 360 dpi printer. The invention provides a method critical to optimization of ink placement based on these variations.
The ability to vary the dimensions of spots and cells in both horizontal and vertical directions also serves to maximize the density of information. For example, with a 200 dpi thermal fax printer, and a 400 dpi scanner, the invention can encode and decode a pattern with cells of 1xc3x972 pixels containing spots of 1xc3x972 pixels, thus encoding over 100 kilobytes of data on a single page. However, a 400 dpi scanner cannot reliably decode a pattern with spots of 1xc3x971 pixels printed at 200 dpi. Since the next step up from 1xc3x971 is 1xc3x972 (or, equivalently, 2xc3x971), the most compact representation is employing the 1xc3x972 cells. If the technology could allow for only square cells, the next step up would be 2xc3x972 cells, which would be only half as compact.
A powerful use of the invention, beyond its ability to communicate and store information (documents, software, graphics, etc.), is as an enabling technology for other technologies. One of the great limiting factors in permitting most consumers to fully exploit their PCs is that the PC possesses simply too many distinct functionalities that must be learned. This is indeed a problem that promises to get only worse as the PC itself develops greater capabilities. Even today, a PC user may have fax and data communication software on the user""s PC, and access to the Internet, and the ability to use the PC as a telephone, and many other functionalities. Yet it is a rare user who sill know how to utilize all of these functionalities. The present invention can be used to encode on paper an arbitrarily complicated batch file, script file, application file, or executable file that can effectively navigate the user through all the complexities involved in each function the PC can perform. By a simple scan of a datatile, for instancexe2x80x94as easy as running a copierxe2x80x94all such functions can be invoked. A datatile can contain both the identity of the application to be invokedxe2x80x94e.g., data communication, fax communication, Internet accessxe2x80x94and the sequence of actions and data that that function requiresxe2x80x94e.g., the phone number that must be dialed, the account number of the user, the password that must be entered, the particular address on the Internet sought, and/or a flag for the particular function that should be performed when access is granted. In effect, the datatile enables paper to become the user interface, instructing the user as to the functions that will be performedxe2x80x94e.g., a bill will be paid over the Internet, or a fax back will be initiated. The scan becomes the single thing that the user must learn to do: all other functions can be performed automatically. This spares the unsophisticated user the perhaps overwhelming task of learning how to invoke these functions, and saves the sophisticated user from the tedium of entering the point clicks and detailed information any of these functions demand.
Several features of the invention""s methods of encoding and decoding make practical for the first time the enabling of many further, simplifying, technologies. The ability to significantly increase density of data allows far more complicated instructions to be placed in any given amount of space. The ability to accommodate a wide audience of printers and scanners allows access to the greatest number of potential users. The ability to vary the shape, dimensions, and location of the encoded digital data on the substrate allows the greatest flexibility in formatting the digital data alongside other information (such as text or graphics) on the substrate.
Further objects and advantages of the invention will become apparent from a consideration of the drawings and ensuing descriptions.